package com.dyz.leetcode._18_backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _47_permuteUnique {
    public List<List<Integer>> permuteUnique(int[] nums) {

        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        if(nums==null|| nums.length==0){return res;}
        Arrays.sort(nums);//去重，必须sort
        dfs(nums, 0, path, res, visited);
        return res;

    }
    private void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> res, boolean[] visited){

        if(path.size()==nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i=0; i<nums.length; i++){
            if(visited[i]){continue;}
            if(i>0 && nums[i]==nums[i-1] && !visited[i-1]){continue;}//减枝

            path.add(nums[i]);
            visited[i] = true;
            dfs(nums, i, path, res, visited);
            path.remove(path.size()-1);
            visited[i] = false;

        }
    }
}
